#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: symmetric.py 
@version:
@time: 2024/01/27 

如果所有镜像对称的位置上两节点都相同，就说明这棵树一定是对称的。

借助队列结构，令需要被比较的两个节点相邻，每次从队列中取出相邻的两个节点进行对比；

如果相同，则继续，如果发现不同，则立即返回结果False。
"""


def symmetric(root):
    if not root:
        return True
    queue = [root.left, root.right]
    while queue:
        root1 = queue.pop()
        root2 = queue.pop()
        # 如果两个节点都是空节点，则继续执行下一轮循环
        if not root1 and not root2:
            continue
        if not root1 or not root2:
            return False
        if root1.val != root2.val:
            return False
        if root1.left or root2.left or root1.right or root2.right:
            queue.append(root1.left)
            queue.append(root2.right)
            queue.append(root1.right)
            queue.append(root2.left)
    return True


"""
dfs方法
递归过程主要在于判断以两个节点为根节点的两棵树是否对称

即是否相等

左子树
   9
  / \
 8   7

右子树
   9
  / \
 8   7 
"""


def symmetric_dfs(root):
    if root:
        return dfs(root.left, root.right)
    return True


def dfs(root1, root2):
    # 节点都不存在，返回True
    if not root1 and not root2:
        return True
    # 节点有一个不存在，返回False
    if not root1 or not root2:
        return False
    # 节点值不相同，返回False
    if root1.val != root2.val:
        return False
    # 　递归调用当前根节点的左右子树
    return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)


class TreeNode:
    def __init__(self, root):
        self.val = root
        self.left = None
        self.right = None


node10 = TreeNode(10)
node91 = TreeNode(9)
node92 = TreeNode(9)
node81 = TreeNode(8)
node82 = TreeNode(8)
node71 = TreeNode(7)
node72 = TreeNode(7)

node10.left = node91
node10.right = node92
node91.left = node81
node91.right = node71
node92.left = node72
node92.right = node82

print(symmetric(node10))
print(symmetric_dfs(node10))
